10189. Разгребатель мин

Рассмотрим игру “разгребатель мин” (minesweeper). Имеется поле, на котором мины обозначены символом ‘*’. Необходимо для каждого пустого поля определить количество соседних полей, содержащих мины.

Вход. Первая строка каждого теста содержит размер поля: количество строк n и столбцов m (0 < n, m £ 100). Следующие n строк описывают состояние поля. Пустая клетка поля обозначается символом ‘.’, клетка с миной – символом ‘*’.

Выход. Для каждого теста вывести входное поле, в каждой пустой (не занятой миной) ячейке которого находится количество мин в соседних с ней клетках.

Пример входа

4 4

*...

....

.*..

....

3 5

**...

.....

.*...

0 0

Пример выхода

Field #1:

*100

2210

1*10

1110

Field #2:

**100

33200

1*100

РЕШЕНИЕ

обработка массива

Анализ алгоритма

Заведем массив res, для которого res[i][j] будет содержать количество соседних мин для позиции (i, j). После прочтения данных, для каждой клетки (i, j) с миной прибавим единицу к каждой соседней c (i, j) клетке в массиве res. Выводим поле, печатая для каждой мины символ ‘*’, а для каждого пустого поля значение res[i][j].

Реализация алгоритма

В массиве matr длины MAX = 102 будем содержать входное поле, массив res будем использовать для подсчета соседних мин.

#define MAX 102

char matr[MAX][MAX], res[MAX][MAX];

Вводим размеры поля m и n.

scanf("%d %d\n",&m,&n);

while(1)

{

Выводим номер теста count. Читаем входное поле в массив matr.

printf("Field #%d:\n",++count);

memset(res,0,sizeof(res));

for(i = 1; i <= m; i++) gets(&matr[i][1]);

Проходим по всем клеткам поля. Для каждой мины прибавим единицу ко всем соседним с ней клеткам в массиве res.

for(i = 1; i <= m; i++)

for(j = 1; j <= n; j++)

if (matr[i][j] == '*')

{

res[i+1][j]++; res[i-1][j]++; res[i][j+1]++; res[i][j-1]++;

res[i+1][j+1]++; res[i-1][j+1]++; res[i-1][j-1]++; res[i+1][j-1]++;

}

Выводим результат. Для каждой мины выводим символ ‘*’, а для каждого пустого поля значение res[i][j].

for(i = 1; i <= m; i++)

{

for(j = 1; j <= n; j++)

if (matr[i][j] == '*') printf("*"); else printf("%d",res[i][j]);

printf("\n");

}

После вывода результата на последний тест не следует выводить пустую строку. Поэтому воспользуемся приведенным ниже кодом.

scanf("%d %d\n",&m,&n);

if (!m && !n) break; else printf("\n");

}